#include "./adj-list.h"
#include "../../stack/model/cir-queue.h"
#include <iostream>

using namespace std;

void createAdList(AdListGraph &adList)
{
	adList.edgeNum = adList.vertexNum = 0;
}

int locateAdVex(AdListGraph &adList, VertexType u)
{
	for (int i = 0; i < adList.vertexNum; i++)
	{
		if (adList.vertex[i].data == u)
		{
			return i;
		}
	}
	return -1;
}

int isAdConnected(AdListGraph &adList, int v, int w)
{
	if (adList.vertex[v].firstNode->adjVex == w)
	{
		return 1;
	}
	return 0;
}

int firstAdjListVex(AdListGraph &adList, int v)
{
	if (adList.vertex[v].firstNode == nullptr)
	{
		return -1;
	}
	return adList.vertex[v].firstNode->adjVex;
}

int nextAdjListVex(AdListGraph &adList, int v, int w)
{
	EdgeNode *pointer = adList.vertex[v].firstNode;
	while (pointer != nullptr)
	{
		if (pointer->adjVex == w)
		{
			return (pointer->next == nullptr) ? -1 : pointer->next->adjVex;
		}
		pointer = pointer->next;
	}
	return -1;
}

void insertAdVex(AdListGraph &adList, VertexType u)
{
	VertexNode *node = (VertexNode *)malloc(sizeof(VertexNode));
	node->data = u;
	node->firstNode = nullptr;
	adList.vertex[adList.vertexNum] = *node;
	adList.vertexNum++;
}

void insertAdArc(AdListGraph &adList, int v, int w, int weight)
{
	EdgeNode *arc = (EdgeNode *)malloc(sizeof(EdgeNode));
	arc->next = nullptr;
	arc->adjVex = w;
	arc->weight = weight;
	EdgeNode *pointer = adList.vertex[v].firstNode;
	if (pointer == nullptr)
	{
		adList.vertex[v].firstNode = arc;
	}
	else
	{
		while (pointer->next != nullptr)
		{
			pointer = pointer->next;
		}
		pointer->next = arc;
	}
	adList.edgeNum++;
}

void DFS(AdListGraph &adList, int i, int *visited, void (*visit)(VertexType &))
{
	// 访问第一个点
	visit(adList.vertex[i].data);
	visited[i] = 1;
	// 然后依次递归访问邻接点
	EdgeNode *pointer = adList.vertex[i].firstNode;
	while (pointer != nullptr)
	{
		if (!visited[pointer->adjVex])
		{
			DFS(adList, pointer->adjVex, visited, visit);
		}
		pointer = pointer->next;
	}
}

void DFSTraverse(AdListGraph &adList, void (*visit)(VertexType &))
{
	// 初始化辅助访问数组
	int *visited = (int *)calloc(adList.vertexNum, sizeof(int));
	for (int i = 0; i < adList.vertexNum; i++)
	{
		visited[i] = 0;
	}
	// 对没访问过的顶点调用DFS
	for (int i = 0; i < adList.vertexNum; i++)
	{
		if (!visited[i])
		{
			DFS(adList, i, visited, visit);
		}
	}
}

void BFSTraverse(AdListGraph &adList, void (*visit)(VertexType &))
{
	// 初始化辅助数组和队列
	CircularQueue queue;
	initCircularQueue(queue);
	int *visited = (int *)calloc(adList.vertexNum, sizeof(int));
	for (int i = 0; i < adList.vertexNum; i++)
	{
		visited[i] = 0;
	}
	// 访问第一个顶点
	EdgeNode *pointer;
	for (int i = 0; i < adList.vertexNum; i++)
	{
		// 访问这个点并加入队列（加入索引）
		if (!visited[i])
		{
			visit(adList.vertex[i].data);
			visited[i] = 1;
			enterCircularQueue(queue, i);
			while (!circularQueueEmpty(queue))
			{
				// 出队然后访问这个点的所有邻接点
				i = goOutCircularQueue(queue);
				pointer = adList.vertex[i].firstNode;
				while (pointer != nullptr)
				{
					if (!visited[pointer->adjVex])
					{
						visit(adList.vertex[pointer->adjVex].data);
						visited[pointer->adjVex] = 1;
						enterCircularQueue(queue, pointer->adjVex);
					}
					pointer = pointer->next;
				}
			}
		}
	}
}

void printAdList(AdListGraph &adList)
{
	EdgeNode *pointer;
	for (int i = 0; i < adList.vertexNum; i++)
	{
		cout << adList.vertex[i].data << "->";
		pointer = adList.vertex[i].firstNode;
		while (pointer != nullptr)
		{
			cout << pointer->adjVex << "->";
			pointer = pointer->next;
		}
		cout << "^" << endl;
	}
}